#include "linux/slab.h"
#include "linux/errno.h"
#include "linux/radix-tree.h"

// 初始化树
void radix_tree_init(struct radix_tree_root *root)
{
    INIT_LIST_HEAD(&root->rnode);
}

int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
{
    struct radix_tree_node *node;;

    node = (struct radix_tree_node *)kmalloc(sizeof (struct radix_tree_node), GFP_KERNEL);
    if (!node)
        return -ENOMEM;

    node->index = index;
    node->item = item;

    list_add_tail(&node->list, &root->rnode);

    return 0;
}

// 查找元素
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
    struct list_head *list;
    struct radix_tree_node *node;

    list_for_each(list, &root->rnode)
    {
        node = list_entry(list, struct radix_tree_node, list);
        if (node->index == index)
            return node->item;
    }

    return NULL;
}

// 删除元素
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
    struct list_head *pos;
    struct list_head *n;
    struct radix_tree_node *node;
    void *item;

    list_for_each_safe(pos, n, &root->rnode)
    {
        node = list_entry(pos, struct radix_tree_node, list);
        if (node->index == index)
        {
            item = node->item;
            list_del(pos);
            kfree(node);
            return item;
        }
    }

    return NULL;
}